Ćwiczenia/1. Ćwiczenia/Zadanie 7. (szukanie sumy).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Dana jest posortowana tablica A[1...n] oraz liczba x. Proszę napisać program, który stwierdza czy istnieją indeksy i oraz j takie, że A[i] +A[j] = x."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementacja algorytmu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ponieważ wiemy, że sekwencja jest posortowana (jeżeli nie jest powiedziane inaczej, zakładamy, że jest to porządek niemalejący), możemy przeszukać tablicę w czasie liniowym. Wynika to stąd, że poruszając się wskaźnikiem od lewej storny sekwencji, w każdym następnym kroku przemieszczamy się na element taki sam lub większy, natomiast przesuwając się wskażnikiem od prawej strony, w każdym następnym kroku przemieszczamy się na element o wartości takiej samej lub mniejszej niż poprzedni. Łatwo można zauważyć, że jeżeli dla bieżącego ułożenia wskażników $ i $ oraz $ j $ suma jest za mała, musimy zwiększyć sumę, przesuwając wskażnik lewy ($ i $) w prawą stronę. Jeżeli ta suma jest zbyt duża, przesuwamy prawy wskażnik ($ j $) w lewo, aby zmniejszyć sumę."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_indices(arr, target_sum):\n",
    "    i = 0\n",
    "    j = len(arr) - 1\n",
    "    \n",
    "    while i < j:\n",
    "        curr_sum = arr[i] + arr[j]\n",
    "        if curr_sum == target_sum: return i, j\n",
    "        if curr_sum < target_sum: i += 1\n",
    "        else: j -= 1\n",
    "            \n",
    "    return None, None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Przykładowy test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#1 Loop:\n",
      "Values: [-47, -43, -40, -39, -37, -36, -34, -31, -25, -24, -20, -19, 0, 1, 14, 27, 31, 33, 39, 40, 40, 47, 47]\n",
      "Target sum: -35\n",
      "Found indices: i=5 (values[5]=-36), j=13 (values[13]=1)\n",
      "#2 Loop:\n",
      "Values: [-49, -42, -41, -32, -23, -21, -14, -8, -5, 0, 1, 1, 5, 6, 8, 16, 20, 21, 29, 30, 30, 31, 40, 49]\n",
      "Target sum: 41\n",
      "Found indices: i=7 (values[7]=-8), j=23 (values[23]=49)\n",
      "#3 Loop:\n",
      "Values: [-34, -29, -19, -13, -9, -5, -1, 20, 36, 37, 49, 49]\n",
      "Target sum: 76\n",
      "Found indices: i=None , j=None \n",
      "#4 Loop:\n",
      "Values: [-50, -49, -26, -18, -16, -13, 8, 38, 46, 48]\n",
      "Target sum: -50\n",
      "Found indices: i=None , j=None \n",
      "#5 Loop:\n",
      "Values: [-48, -39, -33, -33, -33, -25, -24, -19, -16, -14, -2, -1, 8, 8, 13, 13, 21, 21, 31, 39, 45, 50]\n",
      "Target sum: 2\n",
      "Found indices: i=0 (values[0]=-48), j=21 (values[21]=50)\n",
      "#6 Loop:\n",
      "Values: [-50, -46, -37, -36, -34, -32, -28, -28, -19, -15, -15, -12, -10, -6, -2, 7, 11, 11, 16, 21, 24, 24, 27, 32, 37, 39, 39, 41, 46, 46]\n",
      "Target sum: -94\n",
      "Found indices: i=None , j=None \n",
      "#7 Loop:\n",
      "Values: [-45, -42, -36, -36, -30, -17, -11, -10, 2, 15, 18, 46, 50, 50]\n",
      "Target sum: -42\n",
      "Found indices: i=None , j=None \n",
      "#8 Loop:\n",
      "Values: [-49, -40, -24, -12, 16, 25, 25, 25, 29, 32, 49]\n",
      "Target sum: 100\n",
      "Found indices: i=None , j=None \n",
      "#9 Loop:\n",
      "Values: [-44, -39, -34, -34, -28, -27, -27, -26, -24, -17, -14, 0, 1, 2, 6, 7, 7, 13, 14, 22, 23, 23, 29, 44, 47]\n",
      "Target sum: -98\n",
      "Found indices: i=None , j=None \n",
      "#10 Loop:\n",
      "Values: [-49, -32, -25, -23, -6, -3, 0, 2, 8, 9, 15, 20, 23, 43]\n",
      "Target sum: -75\n",
      "Found indices: i=None , j=None \n",
      "#11 Loop:\n",
      "Values: [-47, -45, -45, -45, -30, -27, -25, -13, -11, 7, 9, 11, 25, 30, 31, 45]\n",
      "Target sum: -32\n",
      "Found indices: i=None , j=None \n",
      "#12 Loop:\n",
      "Values: [-45, -39, -35, -25, -5, 2, 17, 20, 24, 24, 25, 29, 36, 38, 39, 39, 42, 45, 50]\n",
      "Target sum: 62\n",
      "Found indices: i=6 (values[6]=17), j=17 (values[17]=45)\n",
      "#13 Loop:\n",
      "Values: [-37, -34, -33, -29, -21, -13, -10, -7, 29, 49, 50]\n",
      "Target sum: -31\n",
      "Found indices: i=4 (values[4]=-21), j=6 (values[6]=-10)\n",
      "#14 Loop:\n",
      "Values: [-47, -44, -36, -35, -34, -27, -26, -16, -12, -9, -4, -3, -1, -1, 10, 13, 16, 17, 24, 25, 30, 34, 34, 36, 41, 43, 44, 48]\n",
      "Target sum: 50\n",
      "Found indices: i=16 (values[16]=16), j=22 (values[22]=34)\n",
      "#15 Loop:\n",
      "Values: [-44, -40, -31, -22, -22, -14, -4, -1, 0, 1, 4, 10, 24, 24, 30, 31, 33, 34, 38, 43, 44]\n",
      "Target sum: 12\n",
      "Found indices: i=2 (values[2]=-31), j=19 (values[19]=43)\n",
      "#16 Loop:\n",
      "Values: [-49, -47, -46, -44, -41, -36, -36, -31, -22, -16, -10, -9, -8, -6, 1, 8, 11, 15, 24, 24, 25, 27, 37, 41, 42, 45, 45, 46, 48, 49]\n",
      "Target sum: -7\n",
      "Found indices: i=0 (values[0]=-49), j=24 (values[24]=42)\n",
      "#17 Loop:\n",
      "Values: [-49, -42, -39, -37, -37, -33, -30, -20, -19, -18, -18, -7, -2, -1, 2, 5, 10, 12, 12, 21, 23, 25, 26, 33, 35, 44]\n",
      "Target sum: 61\n",
      "Found indices: i=22 (values[22]=26), j=24 (values[24]=35)\n",
      "#18 Loop:\n",
      "Values: [-44, -30, -28, -18, -13, -11, -7, -6, 4, 4, 5, 11, 14, 26, 35, 49]\n",
      "Target sum: -33\n",
      "Found indices: i=0 (values[0]=-44), j=11 (values[11]=11)\n",
      "#19 Loop:\n",
      "Values: [-50, -48, -44, -42, -41, -31, -12, -6, -2, 7, 8, 14, 25, 36, 44, 48, 49]\n",
      "Target sum: -18\n",
      "Found indices: i=6 (values[6]=-12), j=7 (values[7]=-6)\n",
      "#20 Loop:\n",
      "Values: [-44, -43, -40, -38, -27, -26, -19, -18, -17, -17, -14, -11, -8, -6, -5, -5, -4, -4, 8, 9, 13, 17, 18, 20, 21, 28, 31, 37]\n",
      "Target sum: -22\n",
      "Found indices: i=1 (values[1]=-43), j=24 (values[24]=21)\n",
      "#21 Loop:\n",
      "Values: [-26, -23, -20, -19, -10, 14, 17, 25, 27, 40, 41]\n",
      "Target sum: -55\n",
      "Found indices: i=None , j=None \n",
      "#22 Loop:\n",
      "Values: [-50, -47, -44, -35, -32, -32, -30, -18, -14, -12, -3, -2, 1, 1, 3, 5, 18, 19, 21, 26, 30, 38, 42, 45, 49]\n",
      "Target sum: 92\n",
      "Found indices: i=None , j=None \n",
      "#23 Loop:\n",
      "Values: [-43, -40, -33, -2, 2, 3, 15, 22, 35, 50]\n",
      "Target sum: 22\n",
      "Found indices: i=None , j=None \n",
      "#24 Loop:\n",
      "Values: [-41, -38, -25, -20, -20, -19, -19, -18, -15, -7, 2, 3, 6, 12, 21, 27, 28, 28, 28, 40, 45, 49]\n",
      "Target sum: 26\n",
      "Found indices: i=5 (values[5]=-19), j=20 (values[20]=45)\n",
      "#25 Loop:\n",
      "Values: [-49, -40, -38, -31, -31, -27, -27, -26, -23, -22, -18, -14, -11, -10, -9, -8, 6, 7, 11, 12, 26, 26, 26, 27, 29, 31, 32, 34, 39, 40]\n",
      "Target sum: -42\n",
      "Found indices: i=0 (values[0]=-49), j=17 (values[17]=7)\n",
      "#26 Loop:\n",
      "Values: [-50, -48, -46, -38, -35, -28, -26, -26, -17, -12, -5, -3, -1, 3, 5, 13, 19, 25, 27, 31, 32, 33, 33, 36, 38, 41, 41]\n",
      "Target sum: -98\n",
      "Found indices: i=0 (values[0]=-50), j=1 (values[1]=-48)\n",
      "#27 Loop:\n",
      "Values: [-48, -42, -41, -36, -23, -20, -15, -15, -14, -10, -2, -2, -1, 9, 12, 17, 20, 22, 23, 30, 34, 40, 41, 46, 48, 49]\n",
      "Target sum: -79\n",
      "Found indices: i=None , j=None \n",
      "#28 Loop:\n",
      "Values: [-48, -43, -30, -28, -28, -25, -16, -14, -13, -12, 1, 6, 25, 32, 36]\n",
      "Target sum: -84\n",
      "Found indices: i=None , j=None \n",
      "#29 Loop:\n",
      "Values: [-38, -32, -32, -30, -26, -24, -3, 19, 23, 23, 32, 32, 34, 41, 46]\n",
      "Target sum: -71\n",
      "Found indices: i=None , j=None \n",
      "#30 Loop:\n",
      "Values: [-48, -39, -35, -24, -19, -18, -14, 5, 19, 40, 42]\n",
      "Target sum: 48\n",
      "Found indices: i=None , j=None \n",
      "#31 Loop:\n",
      "Values: [-40, -34, -25, -22, -18, -16, -9, -8, -8, -5, 2, 9, 42, 42, 44, 48]\n",
      "Target sum: 59\n",
      "Found indices: i=None , j=None \n",
      "#32 Loop:\n",
      "Values: [-35, -27, -12, -11, -6, -6, 1, 19, 29, 33, 38, 46]\n",
      "Target sum: 30\n",
      "Found indices: i=6 (values[6]=1), j=8 (values[8]=29)\n",
      "#33 Loop:\n",
      "Values: [-31, -24, -21, -14, -1, 1, 9, 14, 18, 18, 25, 27, 29, 32, 35, 37, 49]\n",
      "Target sum: 95\n",
      "Found indices: i=None , j=None \n",
      "#34 Loop:\n",
      "Values: [-49, -49, -43, -24, -23, -20, -12, -8, -4, -2, 1, 1, 4, 4, 6, 7, 9, 13, 13, 15, 30, 35, 35, 44, 49]\n",
      "Target sum: 53\n",
      "Found indices: i=12 (values[12]=4), j=24 (values[24]=49)\n",
      "#35 Loop:\n",
      "Values: [-44, -42, -38, -18, -18, -10, 9, 11, 27, 43, 44, 45]\n",
      "Target sum: 41\n",
      "Found indices: i=None , j=None \n",
      "#36 Loop:\n",
      "Values: [-45, -42, -36, -34, -31, -28, -17, -17, -15, -11, -7, -6, 3, 4, 9, 11, 24, 25, 25, 26, 32, 34, 41, 41]\n",
      "Target sum: 54\n",
      "Found indices: i=None , j=None \n",
      "#37 Loop:\n",
      "Values: [-42, -35, -35, -22, -21, -15, -14, 0, 22, 28, 40, 43]\n",
      "Target sum: -32\n",
      "Found indices: i=None , j=None \n",
      "#38 Loop:\n",
      "Values: [-47, -38, -36, -33, -27, -25, -7, -4, 3, 9, 10, 12, 12, 16, 16, 18, 21, 37, 39, 49, 50]\n",
      "Target sum: 48\n",
      "Found indices: i=9 (values[9]=9), j=18 (values[18]=39)\n",
      "#39 Loop:\n",
      "Values: [-44, -42, -35, -32, -14, 21, 26, 35, 40, 41, 42, 49]\n",
      "Target sum: -31\n",
      "Found indices: i=None , j=None \n",
      "#40 Loop:\n",
      "Values: [-49, -43, -33, -29, -28, -23, -20, -16, -9, -9, -1, 1, 2, 6, 11, 13, 20, 28, 28, 36, 36]\n",
      "Target sum: -9\n",
      "Found indices: i=3 (values[3]=-29), j=16 (values[16]=20)\n",
      "#41 Loop:\n",
      "Values: [-48, -44, -21, -4, 0, 3, 7, 17, 20, 40, 42, 42, 47]\n",
      "Target sum: 36\n",
      "Found indices: i=3 (values[3]=-4), j=9 (values[9]=40)\n",
      "#42 Loop:\n",
      "Values: [-48, -42, -28, -27, -24, -24, -17, -11, -11, -7, -4, 3, 3, 8, 9, 14, 18, 28, 35, 41, 43, 49]\n",
      "Target sum: -62\n",
      "Found indices: i=None , j=None \n",
      "#43 Loop:\n",
      "Values: [-49, -45, -43, -43, -42, -39, -30, -29, -25, -23, -22, -17, -12, -11, -9, -1, 5, 8, 11, 15, 19, 19, 35, 38, 43, 44, 44, 46]\n",
      "Target sum: 13\n",
      "Found indices: i=6 (values[6]=-30), j=24 (values[24]=43)\n",
      "#44 Loop:\n",
      "Values: [-50, -42, -41, -37, -30, -25, -16, -11, 8, 9, 13, 13, 19, 24, 25, 49]\n",
      "Target sum: -85\n",
      "Found indices: i=None , j=None \n",
      "#45 Loop:\n",
      "Values: [-46, -40, -39, -34, -28, -26, -22, -20, -15, -15, -11, -9, -7, -3, 4, 8, 11, 13, 16, 25, 36, 45]\n",
      "Target sum: 13\n",
      "Found indices: i=13 (values[13]=-3), j=18 (values[18]=16)\n",
      "#46 Loop:\n",
      "Values: [-47, -46, -42, -38, -17, -7, 6, 23, 28, 45, 45, 48, 49]\n",
      "Target sum: 80\n",
      "Found indices: i=None , j=None \n",
      "#47 Loop:\n",
      "Values: [-45, -45, -42, -42, -41, -40, -37, -24, -19, -11, -10, 2, 16, 18, 22, 45, 46]\n",
      "Target sum: 4\n",
      "Found indices: i=2 (values[2]=-42), j=16 (values[16]=46)\n",
      "#48 Loop:\n",
      "Values: [-48, -45, -42, -41, -39, -34, -30, -30, -29, -25, -24, -20, -11, -1, 6, 8, 8, 8, 11, 11, 16, 17, 19, 31, 39]\n",
      "Target sum: 37\n",
      "Found indices: i=14 (values[14]=6), j=23 (values[23]=31)\n",
      "#49 Loop:\n",
      "Values: [-50, -49, -46, -40, -30, -26, -21, -20, -7, -6, 0, 5, 12, 16, 16, 20, 20, 29, 35, 42, 45, 45]\n",
      "Target sum: -85\n",
      "Found indices: i=None , j=None \n",
      "#50 Loop:\n",
      "Values: [-49, -45, -42, -40, -36, -33, -28, -17, -17, -16, -11, -11, 9, 12, 16, 18, 20, 21, 28, 39, 40, 43]\n",
      "Target sum: 63\n",
      "Found indices: i=16 (values[16]=20), j=21 (values[21]=43)\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "reps = 50\n",
    "for k in range(reps):\n",
    "    values = sorted(random.randint(-50, 50) for _ in range(random.randint(10, 30)))\n",
    "    target_sum = random.randint(-100, 100)\n",
    "    i, j = find_indices(values, target_sum)\n",
    "    print(f'#{k+1} Loop:')\n",
    "    print('Values:', values)\n",
    "    print('Target sum:', target_sum)\n",
    "    val_i = f\"(values[{i}]={values[i]})\" if i is not None else ''\n",
    "    val_j = f\"(values[{j}]={values[j]})\" if j is not None else ''\n",
    "    print(f'Found indices: i={i} {val_i}, j={j} {val_j}')"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}